package demo;
import java.util.List;

class 汉诺塔 {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        han(A, A.size(), B, C);
    }

    private void han(List<Integer> A, int n, List<Integer> B, List<Integer> C) {
        if (n == 1) {
            // 直接把A中的盘子给C
            C.add(A.remove(A.size()-1));
            return;
        }
        // 1、先将n-1个盘子，从A借助C移动到B
        han(A, n-1, C, B);
        // 2、将A中最后一个盘子移动到C
        C.add(A.remove(A.size()-1));
        // 3、最后将B中的n-1个盘子借助A移动到C
        han(B, n-1, A, C);
    }
}

class 合并两个有序链表 {
    // 合并两个有序链表并返回头节点
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 1、函数的截止条件
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        // 2、找到值小的结点作为头
        if (list1.val <= list2.val) {
            // 以list1作为头，合并剩下的链表
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            // 以list2作为头，合并剩下的链表
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

class 反转链表 {
    // 把head链表逆置，并返回新的头节点
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 将head后面的结点翻转，并返回新的结点
        ListNode newHead = reverseList(head.next);
        // 将当前结点的下一个结点的next指针指向当前结点
        head.next.next = head;
        // 并把当前结点的next指针置为null
        head.next = null;
        return newHead;
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode() {

    }

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}